206. 反转链表

题目链接
代码随想录

分析

其实基本思路大家都知道，就是递归，根据题目的意思我们也能确定这个递归方法的怎么写：

• 递归的方法体的内容是反转 next 指针
• 同时返回头节点
  重点是这个反转的过程，正常情况下反转两个节点的指向关系，至少需要两个节点，一个是前一个节点（pre）一个是当前节点（now），但是只用前一个节点（pre）也行，因为当前节点可以通过前一个节点的 next 指针来得到（跟 203. 移除链表元素#解题 中的方法一致），
  此外反转的时候需要同时修改 now 和 pre 两个节点的 next 指针，now 的 next 指向 pre ，pre 的 next 指向 null。我们很容易忽略 pre 的 next 指针，如果不设置 pre 的 next 为 null，反转之后，链表的最后一个节点（原链表的 head）的 next 指针会指向倒数第二个节点，而倒数第二个节点已经指向了最后一个节点，于是形成了回环，这就是 bug。
  而且还要注意，我们应该是先反转后面的节点，后面的节点反转完了，再反转当前节点。
  最终写出的代码如下：

解题

public ListNode reverseList(ListNode head) {
	// 如果输入为 null，那么也返回 null
    if(head==null){
        return null;
    }
    // 因为 reverseList 本身就是递归调用的，因此这里应该把 head 理解为 nowNode
    // 先获取当前节点的下一个节点
    ListNode nextNode = head.next;
    if(nextNode==null){
		// next指针为空，说明是最后一个节点，也就是反转之后的新的head
        // 新的head
        return head;
    }else{
        // 得先反转下一个节点的，然后再反转自己这个节点的，不然先反转自己这个节点，下一个节点就不对了
        ListNode newHead = reverseList(nextNode);
        // 反转分两步
        // 第一步把下一个节点的next指针指向当前节点
        nextNode.next=head;
        //第二步把当前节点的next设置为 null
        // 如果不设置为null，反转之后，链表的最后一个节点（原链表的head）的next指针会指向倒数第二个节点，形成回环
		// 因为之前已经获取了 head.next，所以这里设置为null不影响
		// 而且 head.next会 当前节点的前一个节点的reverseList方法中再次被赋值
        head.next=null;
        return newHead;
    }
}

递归

其实递归没有那么复杂，但是总写不好，三道题套路解决递归问题 这篇博客就写的很好，
递归的过程如下：

递归是一个反复调用自身的过程，这就说明它每一级的功能都是一样的，因此我们只需要关注一级递归的解决过程即可。
如上图所示，我们需要关心的主要是以下三点：

1. 整个递归的终止条件。
2. 一级递归需要做什么？
3. 应该返回给上一级的返回值是什么？
   因此，也就有了我们解递归题的三部曲：
4. 找整个递归的终止条件：递归应该在什么时候结束？
5. 找返回值：应该给上一级返回什么信息？
6. 本级递归应该做什么：在这一级递归中，应该完成什么任务？
   一定要理解这 3 步，这就是以后递归秒杀算法题的依据和思路。
   我们写这一题，也是这样写的。

• 终止条件，找到最后一个节点
• 返回值：反转之后的头节点
• 本机递归应该做什么：反转两个节点（设置 next 指针）

相关题

19. 删除链表的倒数第 N 个结点